import java.util.Arrays;

public class QuickTest {
    public static void main(String[] args) {
        int[] a=new int[]{3,1,2,8,7,4,5,6};
        QuickTest qk=new QuickTest();
        qk.sort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
    private void sort(int[] a,int low,int high){
        if(low>=high) return;//这里是大于等于
        int pivot=partition(a,low,high);
        sort(a,low,pivot-1);
        sort(a,pivot+1,high);
    }

    private int partition(int[] a,int start,int end){
        int pivot=a[start];
        int left=start+1,right=end;
        while(left<right){
            while(left<right&&a[right]>=pivot)
                right--;
            while(left<right&&a[left]<=pivot)
                left++;
            swap(a,left,right);
        }
        swap(a,left,start);
        return left;
    }

    private void swap(int[] a,int p1,int p2){
        int temp=a[p1];
        a[p1]=a[p2];
        a[p2]=temp;
    }

}
